package com.jiang.daily.Q855;

import java.util.*;

/**
 * @author Jiang
 * @version 1.0
 * @date 2024/12/23 18:04
 */
class ExamRoom {
    private int len;
    private int position;
    private TreeSet<Integer> set;

    public ExamRoom(int n) {
        len = n; // 记录座位的数量
        position = 0; // 新来人坐的位置
        set = new TreeSet(); // 初始化TreeSet，默认从大到小排序
    }

    public int seat() {
        set.add(position); // 添加到TreeSet中
        int temp = position;
        setPosition(); // 更新坐的位置
        return temp;
    }

    public void leave(int p) {
        set.remove(p); // 从TreeSet中移除p
        setPosition(); // 更新坐的位置
    }

    private void setPosition() {
        if (set.isEmpty()) { // 如果没人，则更新位置为0
            position = 0;
            return;
        }
        int l = -1; // 左边人的位置
        int distance = 0; // 新位置离人的最远距离
        for (Integer v : set) {
            int r = v; // 右边人的位置
            if (l == -1) { // 如果l == -1， 记录从座位 0 到 第一个人距离并且更改新的位置为0
                distance = r;
                position = 0;
            } else { // 通过左右两人的位置，计算新的位置
                int temp = (l + r) / 2;
                if (temp - l > distance) { // 如果新位置的距离大于最远距离，更新
                    distance = temp - l;
                    position = temp;
                }
            }
            l = r; // 右边人位置在下次循环是左边人的位置
        }
        // 如果最后一个位置到最后一个人的距离大于最远距离，则更新
        if (len - 1 - l > distance) {
            position = len - 1;
        }
    }
}